﻿/*
 * Sample input:
 * 53--7----
 * 6--195---
 * -98----6-
 * 8---6---3
 * 4--8-3--1
 * 7---2---6
 * -6----28-
 * ---419--5
 * ----8--79
 *
 * Expected output:
 * 534678912
 * 672195348
 * 198342567
 * 859761423
 * 426853791
 * 713924856
 * 961537284
 * 287419635
 * 345286179
 */

namespace Sudoku
{
    using System;

    public class Sudoku
    {
        public static void SolveSudoku(int[,] sudoku, int row, int col)
        {
            int[] freePosition = NextPosition(row, col);

            if (sudoku[freePosition[0], freePosition[1]] == 0)
            {
                for (int currentValue = 1; currentValue <= 9; currentValue++)
                {
                    bool isPosibleValue = IsPosibleValue(currentValue, freePosition[0], freePosition[1], sudoku);

                    if (isPosibleValue)
                    {
                        sudoku[freePosition[0], freePosition[1]] = currentValue;
                        if (freePosition[0] == sudoku.GetLength(0) - 1 && freePosition[1] == sudoku.GetLength(1) - 1)
                        {
                            PrintSudoku(sudoku);
                        }

                        SolveSudoku(sudoku, freePosition[0], freePosition[1]);
                        sudoku[freePosition[0], freePosition[1]] = 0;
                    }
                }
            }
            else
            {
                if (freePosition[0] == sudoku.GetLength(0) - 1 && freePosition[1] == sudoku.GetLength(1) - 1)
                {
                    PrintSudoku(sudoku);
                }

                SolveSudoku(sudoku, freePosition[0], freePosition[1]);
            }
        }

        public static void PrintSudoku(int[,] sudoku)
        {
            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                for (int j = 0; j < sudoku.GetLength(1); j++)
                {
                    Console.Write(sudoku[i, j]);
                }
                Console.WriteLine();
            }

            Environment.Exit(0);
        }

        public static int[] NextPosition(int currentRow, int currentCol)
        {
            int[] freePosition = new int[2];

            if (currentCol >= 8)
            {
                freePosition[0] = currentRow + 1;
                freePosition[1] = 0;
            }
            else
            {
                freePosition[0] = currentRow;
                freePosition[1] = currentCol + 1;
            }

            return freePosition;
        }

        public static bool IsPosibleValue(int value, int row, int col, int[,] sudoku)
        {
            bool isPosibleValue = true;

            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                if (sudoku[row, i] == value || sudoku[i, col] == value)
                {
                    isPosibleValue = false;
                    break;
                }
            }

            int currentSquareStartRow = row / 3;
            int currentSquareStartCol = col / 3;

            for (int i = currentSquareStartRow * 3; i < (currentSquareStartRow * 3) + 3; i++)
            {
                for (int j = currentSquareStartCol * 3; j < (currentSquareStartCol * 3) + 3; j++)
                {
                    if (sudoku[i, j] == value)
                    {
                        isPosibleValue = false;
                        return isPosibleValue;
                    }
                }
            }

            return isPosibleValue;
        }

        public static void ReadSudoku(int[,] sudoku)
        {
            for (int i = 0; i < sudoku.GetLength(0); i++)
            {
                string currentLine = Console.ReadLine();
                for (int j = 0; j < currentLine.Length; j++)
                {
                    if (currentLine[j] == '-')
                    {
                        sudoku[i, j] = 0;
                    }
                    else
                    {
                        sudoku[i, j] = int.Parse(currentLine[j].ToString());
                    }
                }
            }
        }

        public static void Main()
        {
            int[,] sudoku = new int[9, 9];
            ReadSudoku(sudoku);
            SolveSudoku(sudoku, 0, -1);
        }
    }
}